#include "tictactoe_duino.h" 
#include <EEPROM.h>

//############################################
//# Library functions	                     #
//############################################

/*
Physical board Layout:
 +----------------+  
 | 1.1 | 1.2 | 1.3| 
 |-----+-----+----|
 | 1.1 | 1.2 | 1.3|
 |-----+-----+----|
 | 1.1 | 1.2 | 1.3|
 +----------------+
 |  G  |
 +-----+
 
 Software board Layout:
 buttonNr and ledNr range from 0 to 9, where 0..8 are the play buttons/led and 9 is the game button/led
 The Game button/led can be used to start a game, choose a random starting player and/or show the current player. 
 +----------------+  
 |  0  |  1  |  2 | 
 |-----+-----+----|
 |  3  |  4  |  5 |
 |-----+-----+----|
 |  6  |  7  |  8 |
 +----------------+
 |  9  |
 +-----+
 
 COLOR: NONE, GREEN, RED, ORANGE     // available colors
 
 initialisation();                   // initialisation of the hardware, has to be done once in setup();
 int check_buttons();                // returns buttonNr
 void set_ledNr(lednr, COLOR);       // enables LED ledNr with color
*/

int player = 1;
int com = 1;
int board[9];
unsigned long nodecount = 0;
unsigned long terminalcount = 0;
unsigned long betacutoffcount = 0;
unsigned long abcount = 0;
unsigned long time;
boolean playing = false;
boolean negamaxx = false;
boolean abPruning = false;
boolean negascott = false;
boolean logs = false;
int possibleWins = 8;

// these positions win
// when occupied from the same player
int wins [8][3] = {
    {0, 1, 2},
    {3, 4, 5},
    {6, 7, 8},
    {0, 3, 6},
    {1, 4, 7},
    {2, 5, 8},
    {0, 4, 8},
    {2, 4, 6}
  };

// Setup runs only once at startup
void setup() {
  
  Serial.begin(9600);
  Serial.flush();
  // initialize hardware timing and I/O functionality to the board
  initialisation();
}

// starts a new game
void reset() {
  
  playing = true;
  player = 1;
  nodecount = 0;
  terminalcount = 0;
  betacutoffcount = 0;
  abcount = 0;

  abPruning = false;
  negamaxx = false;
  negascott = false;
  logs = false;

  for (int i = 0; i < 9; i++) {
    
    set_ledNr(i, NONE);
    board[i] = 0;
  }
  
  //player = (byte) random(1,3);
}

// returns true if n is a terminal node
bool isTerminal(int n[]) {  
  for (int i = 0; i < possibleWins; i++) {
    
    if ((n[wins[i][0]] != 0) && (n[wins[i][0]] == n[wins[i][1]]) && (n[wins[i][0]] == n[wins[i][2]])) {
      terminalcount++;
      return true;
    }
  }
  
  for (int i = 0; i < 9; i++) {
    
    if (n[i] == 0) {
      
      return false;
    }
  }
  
  terminalcount++;
  return true;
}

// returns the minimax value of a position
int minimax(int n[], int p, int* move) {
  nodecount++;  
  //Serial.println("Hello");
  if (isTerminal(n)) {
    
    return valueOf(n);
  }
  
  int alpha, first = 1;
  
  for (int i = 0; i < 9; i++) {
  
    if (n[i] == 0) {
    
      n[i] = p;
      
      int foo;
      int newAlpha = minimax(n, opponentOf(p), &foo);
      
      n[i] = 0;
      
      if (first) {
       
        first = 0;
        alpha = newAlpha;
        *move = i;
        //Serial.println(*move);
      }
      else if ((p == 1) && (newAlpha > alpha)) {
        
        *move = i;
        alpha = newAlpha;
        //Serial.println(*move);
      }
      else if ((p == -1) && (newAlpha < alpha)) {
        
        *move = i;
        alpha = newAlpha;
        //Serial.println(*move);
        
      } 
    }
  }
  
  return alpha;
}

// returns the alphabeta value of a position
int alphabeta(int n[], int p, int alpha, int beta, int* move) {
  nodecount++;  
  //Serial.println("Hello");
  if (isTerminal(n)) {
    
    return valueOf(n);
  }
  
  //int value, first = 1;
  
  for (int i = 0; i < 9; i++) {
  
    if (n[i] == 0) {
    
      n[i] = p;
      
      int foo;
      int newValue = alphabeta(n, opponentOf(p), alpha, beta, &foo);
      
      n[i] = 0;
         
      if (p == 1) {
        
        if (newValue > alpha) {
          
          alpha = newValue;
          *move = i;
        }
        
        if (beta <= alpha) {
          abcount++;          
          break;
        }
      }
      else {
        
        if (newValue < beta) {
          
          beta = newValue;
          *move = i;
        }
        
        if (beta <= alpha) {
          abcount++;
          break;
        }
      }
    }
  }
  
  return (p == 1) ? alpha : beta;
}

int negamax(int n[], int p, int alpha, int beta, int* move) {
  nodecount++;
 // Serial.println("vor Term");
 // Serial.flush();
  //Serial.println("Hello");
  if (isTerminal(n)) {
 //   Serial.println("Term");
//    Serial.flush();
    return negaValueOf(n, p);
  }
  for (int i = 0; i < 9; i++) {
//    Serial.println("for schleife");
    if (n[i] == 0) {
//      Serial.println("Biste drin im If");
      n[i] = p;
      
      int foo;
      int newValue = -negamax(n, opponentOf(p), -beta, -alpha, &foo);

      n[i] = 0;

      if (newValue > alpha) {
//        Serial.println(newValue);
        *move = i;
        alpha = newValue;
      }
        
      if (beta <= alpha) {
        abcount++;  
        return beta;
      }
      

    }
  }
  
  return alpha;
}


int negascout(int n[], int p, int alpha, int beta, int* move) {
  nodecount++;
  Serial.println("vor Term");
  Serial.flush();
  //Serial.println("Hello");
  if (isTerminal(n)) {
    Serial.println("Term");
    Serial.flush();
    return valueOf(n);
  }
  
  int ba = beta;
  int childcount = 0;
  
  for (int i = 0; i < 9; i++) {
  
    if (n[i] == 0) {
	
      n[i] = p;
      
      int foo;
      int newValue = -negascout(n, opponentOf(p), -ba, -alpha, &foo);
      
      n[i] = 0;

      if (alpha < newValue && newValue < beta && childcount > 0) {
        Serial.flush();
        Serial.println("Erste If");
        newValue = -negascout(n, opponentOf(p), -beta, -newValue, &foo);
      }
	  
      if(alpha < newValue && newValue < beta) {
        Serial.flush();
        Serial.print("Zweite If: ");
        Serial.println(i);
        alpha = newValue;
        *move = i;
      }
      if(alpha >= beta) {
        Serial.flush();
        Serial.println("Beta Cutoff");
        betacutoffcount++;
        return alpha;
      }
      Serial.flush();
      Serial.println("Danach");
      ba = alpha + 1;
      childcount++;
    }
  }
  
  return alpha;
}

	
/* function negascout(node, depth, a, �)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    b := �                                             (* initial window is (-�, -a) *)
    foreach child of node
        score := -negascout (child, depth - 1, -b, -a)
        if a < score < � and child is not first child      (* check if null-window failed high *)
            score := -negascout(child, depth - 1, -�, -a)  (* full re-search *)
        a := max(a, score)
        if a = �
            return a                                   (* Beta cut-off *)
        b := a + 1                                     (* set new null window *)
    return a */

// returns the value of a board
// 1: player1 won the game
// 2: player2 won the game
// 0: no winner (yet)
int valueOf(int b[]) {
//  Serial.println("jo");
  // goes through all possible win positions
  // and if possible returns the winner
  for (int i = 0; i < possibleWins; i++) {
    
    int winner = b[wins[i][0]];
//    Serial.println("japp");
    if ((winner != 0) && (winner == b[wins[i][1]]) && (winner == b[wins[i][2]])) {
      
      return winner;
    }
  }
  
  return 0;
}

int negaValueOf(int b[], int p) {
//  Serial.println("jo");
  // goes through all possible win positions
  // and if possible returns the winner
  for (int i = 0; i < possibleWins; i++) {
    
    int winner = b[wins[i][0]];
//    Serial.println("japp");
    if ((winner != 0) && (winner == b[wins[i][1]]) && (winner == b[wins[i][2]])) {
      
      return (winner == p) ? winner : opponentOf(winner);
    }
  }
  
  return 0;
}

// advances the player to move next
void nextPlayer() {
  
  player = (player == 1) ? -1 : 1;
}

// returns the opponent of p
int opponentOf(int p) {
  
  return (p == 1) ? -1 : 1;
}

void rainbowUnicorn() {
  for(int i = 0; i < 9; i++) {
    set_ledNr(i,NONE);
  }
  
  set_ledNr(0,GREEN);
  set_ledNr(2,GREEN);
  set_ledNr(6,GREEN);
  set_ledNr(8,GREEN);
  
  delay(200);
  
  for(int i = 0; i < 4; i++) {

    set_ledNr(1,GREEN);
    set_ledNr(3,GREEN);
    set_ledNr(5,GREEN);
    set_ledNr(7,GREEN);
    
    delay(200);
    
    set_ledNr(0,RED);
    set_ledNr(2,RED);
    set_ledNr(6,RED);
    set_ledNr(8,RED);
    
    set_ledNr(4,GREEN);
    
    delay(200);
    
    set_ledNr(1,RED);
    set_ledNr(3,RED);
    set_ledNr(5,RED);
    set_ledNr(7,RED); 
    
    delay(200);
    
    set_ledNr(0,GREEN);
    set_ledNr(2,GREEN);
    set_ledNr(6,GREEN);
    set_ledNr(8,GREEN);
    
    set_ledNr(4,RED);
    
    delay(200);
  }
  
}

// loop() is a replacement for main()
void loop() {
  int incomingByte;
  boolean active = true;
  Serial.println("Welcome to another Tic Tac Toe game.");    
  Serial.print("Initializing...");
  time = millis();
  reset();  
  Serial.print(" ... completed in ");
  Serial.print((millis()-time));
  Serial.println(" ms.");
  Serial.println(" -------------------------------------------------------------------------- ");
  Serial.println("| Which game mode would you like:                                          |");
  Serial.println("| 1 - Standard Minimax, Computer plays first move                          |");
  Serial.println("| 2 - Standard Minimax, with alpha-beta pruning, Computer plays first move |");
  Serial.println("| 3 - Standard Minimax, You play first move                                |");
  Serial.println("| 4 - Standard Minimax, with alpha-beta pruning, You play first move       |");
  Serial.println("| 5 - Experimental mode                                                    |");
//  Serial.println("h - Entering 'h' will display help. ");
  Serial.println(" -------------------------------------------------------------------------- ");
  Serial.println("| Additional Options:                                                      |");
  Serial.println("|                                                                          |");
  Serial.println("| l - Add an l to your mode choice to get more stats                       |");  
  Serial.println(" -------------------------------------------------------------------------- ");
  while(Serial.available() <= 0) {
    delay(10);
  }
  incomingByte = Serial.read();
  switch(incomingByte) {
    case '1': abPruning = false; com = 1; Serial.println("Mode 1 chosen."); break;
    case '2': abPruning = true; com = 1; Serial.println("Mode 2 chosen."); break;
    case '3': abPruning = false; com = -1; Serial.println("Mode 3 chosen."); break;
    case '4': abPruning = true; com = -1; Serial.println("Mode 4 chosen."); break;
    case '5': abPruning = false; com = 1; negascott = false; negamaxx = true; Serial.println("Experimental mode chosen."); break;
    case 'h': Serial.println("Displaying Help, please wait."); break;
  }
  if(Serial.available() > 0) {
    incomingByte = Serial.read();
    if(incomingByte == 'l') {
      Serial.println("Logs are enabled.");
      logs = true;
    }      
  }
  Serial.println();
  Serial.println("Game started.");
  while(!isTerminal(board) && active) {
    nodecount = 0;
    terminalcount = 0;
    abcount = 0;
    betacutoffcount = 0;
    
    if (player == com) {
      Serial.println("Computer to move.");
      time = millis();    
      
      //set_ledNr(9, ORANGE);
      
      int bar;
      
      //Serial.println(move);
      
      int val = 0;
      if(abPruning) {
        val = alphabeta(board, player, -INFINITY, INFINITY, &bar);
      } else if(negamaxx) {
        val = negamax(board, player, -INFINITY, INFINITY, &bar);
      } else if(negascott) {
        val = negascout(board, player, -INFINITY, INFINITY, &bar);
      } else {
        val = minimax(board, player, &bar);
      }
      
      int color = (player == 1) ? GREEN : RED;
      
      board[bar] = player;
      set_ledNr(bar, color);
      
      unsigned long duration = millis()-time;
      
      Serial.print("Computer: Marking Field ");
      Serial.print(bar);
      Serial.print(", calculated in ");
      Serial.print(((int) (duration+500)/1000),DEC);
      Serial.print("s. (");
      Serial.print(duration);
      Serial.println("ms)");
      
      if(logs) {
        Serial.print("Computer: Searched through ");
        Serial.print(nodecount);
        Serial.print(" nodes in the game tree, of which ");
        Serial.print(terminalcount);
        Serial.println(" nodes were terminal nodes.");
  
        if(abPruning) {
          Serial.print("Computer: alpha-beta pruning pruned at ");
          Serial.print(abcount);
          Serial.println(" branches.");
        }
		
        if(negascott) {
          Serial.print("Computer: negascout performed ");
          Serial.print(betacutoffcount);
          Serial.println(" beta cut-offs.");
	}
      }
      nextPlayer();
      
    }
    
    
    else {
      Serial.println("Human to move.");
      time = millis();
      int pressedButton = check_buttons();
      while(pressedButton == -1) {
        delay(10);
        pressedButton = check_buttons();
      }
      if(pressedButton == 9) {
        Serial.println("Game is being reset...");
        reset();
        active = false;
        Serial.println("Goodbye.");
        Serial.println();
      }  
      if (board[pressedButton] == 0) {
        
        int color = (player == 1) ? GREEN : RED;
        
        board[pressedButton] = player;
        set_ledNr(pressedButton, color);
        unsigned long duration = millis() - time;
        Serial.print("Human: Marking Field ");
        Serial.print(pressedButton);
        Serial.print(", determined in ");
        Serial.print(((int) (duration+500)/1000),DEC);
        Serial.print("s. (");
        Serial.print(duration);
        Serial.println("ms)");

        nextPlayer();
      }
    }
  }
  Serial.println("Game is over.");
  int pressedButton = check_buttons();
  while(pressedButton == -1) {
    delay(10);
    pressedButton = check_buttons();
  }
  if(pressedButton == 9) {
    Serial.println("Game is being reset...");
    reset();
    active = false;
    Serial.println("Goodbye.");
    rainbowUnicorn();
    Serial.println();
  }  
}
